package pri.zjy.tree;

import pri.zjy.tree.model.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author zhangjy
 * @description 层序遍历
 * @date 2025/3/13 15:56
 */
public class LevelOrder_102 {

    public static void main(String[] args) {

    }

    /**
     * 广度优先搜索（DFS）；队列实现
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;

        // 待访问的节点
        Queue<TreeNode> queue = new LinkedList<>();
        List<Integer> levelVals = new ArrayList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            levelVals = new ArrayList<>();
            // 每层遍历次数（处理本层数据前要先记录本层的遍历次数，因为遍历过程中queue长度会改变）
            int currentLevelSize = queue.size();
            // 每次记录一层的数据
            for (int i = 0; i < currentLevelSize; i++) {
                // 出队时记录节点值
                TreeNode node = queue.poll();
                levelVals.add(node.val);

                // 记录本层的所有孩子节点，左右节点分别入队（非空入队）
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            res.add(levelVals);
        }
        return res;
    }

}
